package com.链表;

/**
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 反转链表2 {
   static class Solution {
       ListNode behind = null; //后驱结点

       /**
        * 反转前N个结点
        *
        * 
        * @param head
        * @param n
        * @return
        */
       public ListNode reserveN(ListNode head,int n ){
           if(n == 1){
               behind  = head.next;
               return  head;
           }
           ListNode last = reserveN(head.next,n-1);
           head.next.next = head;
           head.next = behind;
           return  last;
       }

       /**
        * 反转链表
        * @param head
        * @return
        */
       public ListNode reserve(ListNode head ){
        if(head.next == null){
            return head;
        }
        ListNode last =  reserve(head.next);
        head.next.next = head;
        head.next  = null;
        return last;

       }


        public ListNode reverseBetween(ListNode head, int m, int n) {
          if(m == 1){
              return reserveN(head,n);
          }
          head.next = reverseBetween(head.next,m-1,n-1);
          return head;
        }
    }

    public static void main(String[] args) {
       Solution solution = new Solution();
        ListNode head = new ListNode(new int[]{1,2,3,4,5});
       //solution.reverseBetween(head,1,1);
//      ListNode node = solution.reserve(head);
//        System.out.println(node.toString());
      ListNode node = solution.reverseBetween(head,2,3);
        System.out.println(node.toString());
    }
}

